package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.ListNode;

import java.util.HashSet;
import java.util.Set;

public class _022_剑指OfferII链表中环的入口节点 {

    // 空间复杂度
    // 数学双指针
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 双指针移动
        do {
            if (fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
        } while (fast != slow);
        fast = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

    // 使用HashMap，记录地址位置，重复则存在环
    // 存在空间复杂度
    public ListNode detectCycle1(ListNode head) {
        Set<ListNode> containers = new HashSet<>();
        while (head != null && !containers.contains(head)) {
            containers.add(head);
            head = head.next;
        }
        return head;
    }

}
